// https://www.lintcode.com/problem/convert-bst-to-greater-tree/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the new root
     */
    public TreeNode convertBST(TreeNode root) {
        // write your code here
        // 非递归实现参考Python版本
        int[] sum = new int[]{0}; // Integer居然是传值的，坑！
        convert(root, sum);
        return root;
    }
    
    protected void convert(TreeNode node, int[] sum) {
        if (node != null) {
            convert(node.right, sum);
            node.val += sum[0];
            sum[0] = node.val;
            convert(node.left, sum);
        }
    }
}